class Solution {
public:
    int countArrangement(int n)
    {
        int ans = 0;
        vector<bool> check(n + 1, false);
        function<void(int)> dfs = [&](int i) {
            if (i == n + 1)
            {
                ans++;
                return;
            }
            for (int j = 1; j <= n; j++)
            {
                if (!check[j])
                {
                    if (j % i == 0)
                    {
                        check[j] = true;
                        dfs(i + 1);
                        check[j] = false;
                    }
                    else if (i % j == 0)
                    {
                        check[j] = true;
                        dfs(i + 1);
                        check[j] = false;
                    }
                }
            }
            };
        dfs(1);
        return ans;
    }
};